package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/reorder-list/">重排链表 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-22 13:57
 */
public class ReorderList_143 {

  // 从start一直反转到最后一个，并返回反转后新的头结点
  public static ListNode reverseToEnd(ListNode start) {
    ListNode pre = null;
    ListNode cur = start;
    ListNode nex = start;
    while (cur != null) {
      nex = cur.next;
      cur.next = pre;
      pre = cur;
      cur = nex;
    }
    return pre;
  }

  // 合并交替各元素
  public static void combine2List(ListNode l1, ListNode l2) {
    ListNode head1 = l1, head2 = l2;
    ListNode nex1 = l1, nex2 = l2;

    while (head1 != null) { // 左边端点长度一定大于右边，根据前边分隔算法
      nex1 = head1.next; // 长链表先记录下一个
      if (head2 != null) {
        head1.next = head2; // 指向l2端
        nex2 = head2.next; // 保存l2链的下一个
        head2.next = nex1; // 指向l1端
        head2 = nex2; // 下移l2端当前头结点
      }
      head1 = nex1;
    }
  }

  /**
   * 核心方法：通过快慢指针找到链表中间节点，并拆分成两个链表，反转第二个链表后，交替合并两个链表
   */
  public void reorderList(ListNode head) {
    ListNode slow = head, fast = head; // 快慢指针

    // 通过slow找到链表的中间节点
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next; // 快指针走两步
    }
    // 拆分为两个链表
    assert slow != null;
    ListNode part2Head = slow.next;
    slow.next = null; // 断开第一个链表
    // 反转第二段链表
    part2Head = reverseToEnd(part2Head);

    // 两个链表合并交替
    combine2List(head, part2Head);
  }
}
